package com.njupt.tanXin;

import java.util.Arrays;

/**
 * 53. 最大子数组和
 */
public class MaxSubArray {


    /**
     * 贪心法：从前往后依次遍历数组中的元素，依次累加当前遍历的元素，如果大于max，max赋值为当前累加的值
     *          加上当前的值减小的，就不修改max，直到当前累加的值小于等于0，从当前位的后一位开始累加
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
       int max = Integer.MIN_VALUE;
       int current = 0;
        for (int i = 0; i < nums.length; i++) {
            current += nums[i];
            if(current>max){
                max = current;
            }
            if(current<=0){
                current = 0;
            }
        }
        return max;
    }

    /**
     * 暴力解：这里是将i，j和的一边计算，一边比较max，最终的效果是一样
     * @param nums
     * @return
     */

    public int maxSubArray2(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }

        int max = Integer.MIN_VALUE;
        int current;
        for (int i = 0; i < nums.length; i++) {
            current = 0;
            for (int j = i; j < nums.length; j++) {
               current += nums[j];
               max = current > max? current : max;
            }
        }

        return max;
    }

    /**
     * 法一：暴力解
     * 这里是将 i到j所有的数字和算好之后在和max比较，
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }

        int max = Integer.MIN_VALUE;
        int current;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                current = sumSubArray(nums,i,j);
                if(current>max){
                    max = current;
                }
            }
        }

        return max;
    }

    public int sumSubArray(int[] nums,int startIndex,int endIndex){
        int sum = 0;
        for (int i = startIndex; i <= endIndex ; i++) {
            sum += nums[i];
        }
        return sum;
    }

    /**
     * 法二：动态规划
     * dp数组的含义：dp[i],以下标i结尾的nums[i]的 最大连续子序列和位dp[i]
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums){
        int max = nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i] , nums[i]);
            max = dp[i]>max ? dp[i] : max;
        }
        return max;
    }

    public int maxSubArray4(int[] nums){

        int dp[][] = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = nums[i];
        }
        for (int j = 1; j < dp[0].length; j++) {
            for (int i = 0; i < j; i++) {
                dp[i][j] = Math.max(MAX(dp,i,j-1)+ nums[j],nums[j]);
            }
        }

        print(dp);
        //遍历dp数组，取最大值
        int start = -1;
        int end = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            for (int j = i; j < dp[0].length ; j++) {
                if(dp[i][j]>max){
                    max = dp[i][j];
                    start = i;
                    end = j;
                }
            }
        }
        System.out.println(start+ "," + end);
        return max;
    }

    public int MAX(int[][] dp,int start ,int end){
        int max = Integer.MIN_VALUE;
        for(int i=start;i<=end;i++){
            max = dp[i][end] > max ?dp[i][end]:max;
        }
        return max;
    }

    public void print(int[][] dp){
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] nums = {1};
        MaxSubArray test = new MaxSubArray();
        System.out.println(test.maxSubArray1(nums));
    }
}
